home *** CD-ROM | disk | FTP | other *** search
/ Mac Easy 2010 May / Mac Life Ubuntu.iso / casper / filesystem.squashfs / usr / src / linux-headers-2.6.28-15 / include / linux / radix-tree.h < prev    next >
Encoding:
C/C++ Source or Header  |  2009-09-09  |  6.7 KB  |  194 lines
  1. /*
  2.  * Copyright (C) 2001 Momchil Velikov
  3.  * Portions Copyright (C) 2001 Christoph Hellwig
  4.  * Copyright (C) 2006 Nick Piggin
  5.  *
  6.  * This program is free software; you can redistribute it and/or
  7.  * modify it under the terms of the GNU General Public License as
  8.  * published by the Free Software Foundation; either version 2, or (at
  9.  * your option) any later version.
  10.  * 
  11.  * This program is distributed in the hope that it will be useful, but
  12.  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14.  * General Public License for more details.
  15.  * 
  16.  * You should have received a copy of the GNU General Public License
  17.  * along with this program; if not, write to the Free Software
  18.  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19.  */
  20. #ifndef _LINUX_RADIX_TREE_H
  21. #define _LINUX_RADIX_TREE_H
  22.  
  23. #include <linux/preempt.h>
  24. #include <linux/types.h>
  25. #include <linux/kernel.h>
  26. #include <linux/rcupdate.h>
  27.  
  28. /*
  29.  * An indirect pointer (root->rnode pointing to a radix_tree_node, rather
  30.  * than a data item) is signalled by the low bit set in the root->rnode
  31.  * pointer.
  32.  *
  33.  * In this case root->height is > 0, but the indirect pointer tests are
  34.  * needed for RCU lookups (because root->height is unreliable). The only
  35.  * time callers need worry about this is when doing a lookup_slot under
  36.  * RCU.
  37.  */
  38. #define RADIX_TREE_INDIRECT_PTR    1
  39. #define RADIX_TREE_RETRY ((void *)-1UL)
  40.  
  41. static inline void *radix_tree_ptr_to_indirect(void *ptr)
  42. {
  43.     return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR);
  44. }
  45.  
  46. static inline void *radix_tree_indirect_to_ptr(void *ptr)
  47. {
  48.     return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
  49. }
  50.  
  51. static inline int radix_tree_is_indirect_ptr(void *ptr)
  52. {
  53.     return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR);
  54. }
  55.  
  56. /*** radix-tree API starts here ***/
  57.  
  58. #define RADIX_TREE_MAX_TAGS 2
  59.  
  60. /* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */
  61. struct radix_tree_root {
  62.     unsigned int        height;
  63.     gfp_t            gfp_mask;
  64.     struct radix_tree_node    *rnode;
  65. };
  66.  
  67. #define RADIX_TREE_INIT(mask)    {                    \
  68.     .height = 0,                            \
  69.     .gfp_mask = (mask),                        \
  70.     .rnode = NULL,                            \
  71. }
  72.  
  73. #define RADIX_TREE(name, mask) \
  74.     struct radix_tree_root name = RADIX_TREE_INIT(mask)
  75.  
  76. #define INIT_RADIX_TREE(root, mask)                    \
  77. do {                                    \
  78.     (root)->height = 0;                        \
  79.     (root)->gfp_mask = (mask);                    \
  80.     (root)->rnode = NULL;                        \
  81. } while (0)
  82.  
  83. /**
  84.  * Radix-tree synchronization
  85.  *
  86.  * The radix-tree API requires that users provide all synchronisation (with
  87.  * specific exceptions, noted below).
  88.  *
  89.  * Synchronization of access to the data items being stored in the tree, and
  90.  * management of their lifetimes must be completely managed by API users.
  91.  *
  92.  * For API usage, in general,
  93.  * - any function _modifying_ the tree or tags (inserting or deleting
  94.  *   items, setting or clearing tags) must exclude other modifications, and
  95.  *   exclude any functions reading the tree.
  96.  * - any function _reading_ the tree or tags (looking up items or tags,
  97.  *   gang lookups) must exclude modifications to the tree, but may occur
  98.  *   concurrently with other readers.
  99.  *
  100.  * The notable exceptions to this rule are the following functions:
  101.  * radix_tree_lookup
  102.  * radix_tree_lookup_slot
  103.  * radix_tree_tag_get
  104.  * radix_tree_gang_lookup
  105.  * radix_tree_gang_lookup_slot
  106.  * radix_tree_gang_lookup_tag
  107.  * radix_tree_gang_lookup_tag_slot
  108.  * radix_tree_tagged
  109.  *
  110.  * The first 7 functions are able to be called locklessly, using RCU. The
  111.  * caller must ensure calls to these functions are made within rcu_read_lock()
  112.  * regions. Other readers (lock-free or otherwise) and modifications may be
  113.  * running concurrently.
  114.  *
  115.  * It is still required that the caller manage the synchronization and lifetimes
  116.  * of the items. So if RCU lock-free lookups are used, typically this would mean
  117.  * that the items have their own locks, or are amenable to lock-free access; and
  118.  * that the items are freed by RCU (or only freed after having been deleted from
  119.  * the radix tree *and* a synchronize_rcu() grace period).
  120.  *
  121.  * (Note, rcu_assign_pointer and rcu_dereference are not needed to control
  122.  * access to data items when inserting into or looking up from the radix tree)
  123.  *
  124.  * radix_tree_tagged is able to be called without locking or RCU.
  125.  */
  126.  
  127. /**
  128.  * radix_tree_deref_slot    - dereference a slot
  129.  * @pslot:    pointer to slot, returned by radix_tree_lookup_slot
  130.  * Returns:    item that was stored in that slot with any direct pointer flag
  131.  *        removed.
  132.  *
  133.  * For use with radix_tree_lookup_slot().  Caller must hold tree at least read
  134.  * locked across slot lookup and dereference.  More likely, will be used with
  135.  * radix_tree_replace_slot(), as well, so caller will hold tree write locked.
  136.  */
  137. static inline void *radix_tree_deref_slot(void **pslot)
  138. {
  139.     void *ret = rcu_dereference(*pslot);
  140.     if (unlikely(radix_tree_is_indirect_ptr(ret)))
  141.         ret = RADIX_TREE_RETRY;
  142.     return ret;
  143. }
  144. /**
  145.  * radix_tree_replace_slot    - replace item in a slot
  146.  * @pslot:    pointer to slot, returned by radix_tree_lookup_slot
  147.  * @item:    new item to store in the slot.
  148.  *
  149.  * For use with radix_tree_lookup_slot().  Caller must hold tree write locked
  150.  * across slot lookup and replacement.
  151.  */
  152. static inline void radix_tree_replace_slot(void **pslot, void *item)
  153. {
  154.     BUG_ON(radix_tree_is_indirect_ptr(item));
  155.     rcu_assign_pointer(*pslot, item);
  156. }
  157.  
  158. int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
  159. void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
  160. void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
  161. void *radix_tree_delete(struct radix_tree_root *, unsigned long);
  162. unsigned int
  163. radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
  164.             unsigned long first_index, unsigned int max_items);
  165. unsigned int
  166. radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
  167.             unsigned long first_index, unsigned int max_items);
  168. unsigned long radix_tree_next_hole(struct radix_tree_root *root,
  169.                 unsigned long index, unsigned long max_scan);
  170. int radix_tree_preload(gfp_t gfp_mask);
  171. void radix_tree_init(void);
  172. void *radix_tree_tag_set(struct radix_tree_root *root,
  173.             unsigned long index, unsigned int tag);
  174. void *radix_tree_tag_clear(struct radix_tree_root *root,
  175.             unsigned long index, unsigned int tag);
  176. int radix_tree_tag_get(struct radix_tree_root *root,
  177.             unsigned long index, unsigned int tag);
  178. unsigned int
  179. radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
  180.         unsigned long first_index, unsigned int max_items,
  181.         unsigned int tag);
  182. unsigned int
  183. radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
  184.         unsigned long first_index, unsigned int max_items,
  185.         unsigned int tag);
  186. int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag);
  187.  
  188. static inline void radix_tree_preload_end(void)
  189. {
  190.     preempt_enable();
  191. }
  192.  
  193. #endif /* _LINUX_RADIX_TREE_H */
  194.